package wish.sequencealignment;

import java.util.ArrayList;
import java.util.List;

import wish.regularExpression.DisjunctiveElement;
import wish.regularExpression.EmptyElement;
import wish.regularExpression.MultipleElements;
import wish.regularExpression.OptionalElement;
import wish.regularExpression.RegularExpressionElement;
import wish.regularExpression.SingleElement;

public class ScoreSequenceAlignment {

	public RegularExpressionElement[] align(RegularExpressionElement[] root, RegularExpressionElement[] toAlign){

		long[][] alignment = new long[root.length+1][toAlign.length+1];

		for (int i = 1; i <= root.length; i++) {
			alignment[i][0] = alignment[i-1][0]+costGapToAlign(root[i-1],toAlign[0]);
		}
		
		for (int j = 1; j <= toAlign.length; j++) {
			alignment[0][j] = alignment[0][j-1]+costGapRoot(root[0],toAlign[j-1]);
		}
		
		long north,west,northwest;
		
		for (int i = 1; i <= root.length; i++) {
			
			for (int j = 1; j <= toAlign.length; j++) {
				
				//Initialize by north
				
				north = alignment[i-1][j] + costGapToAlign(root[i-1],toAlign[j-1]);
				
				//try to align by west
				
				west = alignment[i][j-1] + costGapRoot(root[i-1],toAlign[j-1]);
				
				//northwest
				
				northwest = alignment[i-1][j-1] + matchScore(root[i-1],toAlign[j-1]);
				
				if (north > west && north > northwest){
					
					alignment[i][j] = north;
					
				} else if (west > north && west > northwest){
					
					alignment[i][j] = west;
					
				}else{
					
					alignment[i][j] = northwest;
					
				}
				
			}
			
		}
		
		return generateMatch(alignment,root,toAlign);
		
	}

	private RegularExpressionElement[] generateMatch(long[][] alignment,
			RegularExpressionElement[] root, RegularExpressionElement[] toAlign) {
		//TODO Auto-generated method stub
				
		for (int i = 0; i <= root.length; i++) {
			
			for (int j = 0; j <= toAlign.length; j++) {
				
				System.out.print("\t" + alignment[i][j]);
				
			}
			
			System.out.println("");
			
		}
		
		int i = root.length;

		int j = toAlign.length;
		
		ArrayList<RegularExpressionElement> ar = new ArrayList<RegularExpressionElement>();

		while (i!=0 && j!=0){
		
			RegularExpressionElement a = new EmptyElement(), b = new EmptyElement();
			
			//northwest
			
			long northwest = alignment[i-1][j-1];
			
			long west = alignment[i][j-1];
			
			long north = alignment[i-1][j];
			
			if (northwest > west && northwest > north){
				
				i = i-1;

				j = j-1;
				
				a = root[i];
				
				b = toAlign[j];

				//Data that it's not the same, it's disjunctive.
//				if (!a.equals(b)){
//					
//					ar.add(0, a);
//					
//					br.add(0, "-");
//					
//					ar.add(0, "-");
//					
//					br.add(0, b);
//					
//					continue;
//				} 
				
			} else if (west > northwest && west > north){
				
				j = j-1;
				
				b = toAlign[j];

			} else {
				
				i = i-1;
			
				a = root[i];
				
			}

			ar.add(0, generateRegularExpression(a,b));
			
		}
		
		System.out.println(i + " - " + j);
		
		if (i>=1){
			
			while (i > 0){
			
				i = i-1;
				
				ar.add(0,generateRegularExpression(root[i],new EmptyElement()));
	
			}
			
		}else{ //j > 1
			
			while (j > 0){
				j = j-1;
	
				ar.add(0,generateRegularExpression(new EmptyElement(),toAlign[j]));
	
			}
		}
		
		System.out.println("");
		
		for (RegularExpressionElement string : ar) {
			
			System.out.print(string);
			
		}

		return ar.toArray(new RegularExpressionElement[0]);

	}

	private RegularExpressionElement generateRegularExpression(
			RegularExpressionElement root, RegularExpressionElement toAlign) {

		System.out.println(root + " - " + toAlign);
		
		if (root.matches(toAlign)){
			
			return getMostGeneral(root,toAlign); //can only happen with *
		} else {
			if (root instanceof EmptyElement){
				return new OptionalElement(toAlign);
			} else if (toAlign instanceof EmptyElement){
				return new OptionalElement(root);
			} else {
				
				DisjunctiveElement ret = new DisjunctiveElement();
				ret.addElement(root);
				ret.addElement(toAlign);
				
				return ret;
				
			}
		}

	}

	private RegularExpressionElement getMostGeneral(
			RegularExpressionElement root, RegularExpressionElement toAlign) {
	
		return root.expand(toAlign);
	
	}

	private long matchScore(RegularExpressionElement regularExpressionElement,
			RegularExpressionElement regularExpressionElement2) {
		// TODO Auto-generated method stub
		if (regularExpressionElement.matches(regularExpressionElement2))
			return 3;
		return -3;
	}

	private long costGapRoot(RegularExpressionElement root, RegularExpressionElement toAlign) {
		if (root.isMultipleMatch() && root.matches(toAlign))
			return 2;
		return -2;
	}

	private long costGapToAlign(
			RegularExpressionElement root, RegularExpressionElement toAlign) {
		if (toAlign.isMultipleMatch() && toAlign.matches(root))
			return 1;
		return -1;
	}
	
	public static void main(String[] args) {
		//babababa
		SingleElement a0 = new SingleElement("G");
		MultipleElements a1 = new MultipleElements(new SingleElement("C"));
		SingleElement a2 = new SingleElement("T");
		SingleElement a3 = new SingleElement("C");
		SingleElement a4 = new SingleElement("T");
		SingleElement a5 = new SingleElement("A");
		SingleElement a6 = new SingleElement("G");
		SingleElement a7 = new SingleElement("C");
		SingleElement a8 = new SingleElement("G");

		//abababab
		
		SingleElement b0 = new SingleElement("G");
		SingleElement b1 = new SingleElement("C");
		SingleElement b2 = new SingleElement("G");
		SingleElement b3 = new SingleElement("C");
		MultipleElements b4 = new MultipleElements(new SingleElement("A"));
		SingleElement b5 = new SingleElement("G");
		SingleElement b6 = new SingleElement("T");
		SingleElement b7 = new SingleElement("G");
		
		RegularExpressionElement[] a = new RegularExpressionElement[9];
		RegularExpressionElement[] b = new RegularExpressionElement[8];
		
		a[0] = a0;
		a[1] = a1;
		a[2] = a2;
		a[3] = a3;
		a[4] = a4;
		a[5] = a5;
		a[6] = a6;
		a[7] = a7;
		a[8] = a8;
		
		b[0] = b0;
		b[1] = b1;
		b[2] = b2;
		b[3] = b3;
		b[4] = b4;
		b[5] = b5;
		b[6] = b6;
		b[7] = b7;
		
		new ScoreSequenceAlignment().align(a, b);
		
	}
	
}
